package animation.sort.algorithms;

import java.util.Arrays;

import animation.sort.MergeSortAnimation;
import animation.core.AlgorithmMonitorModel;


/**
 * Created by IntelliJ IDEA.
 * User: emilio
 * Date: Aug 14, 2004
 * Time: 1:23:57 PM
 * To change this template use File | Settings | File Templates.
 */
public class MergeSort
        extends MergeSortAnimation
{

    public String toString()
    {
        return "Merge Sort";
    }

    protected void sort(int array[])
            throws Exception
    {
        initAuxArray(array.length);
        Arrays.fill(array, 0);
        sort(array, 0, array.length - 1);
    }

    void sort(int array[], int low, int high)
            throws Exception
    {

        if (low < high) {
            markBox(low, high+1);
            doSleep(1000);

            int mid = (low + high) / 2;

            sort(array, low, mid);
            sort(array, mid + 1, high);
            merge(array, low, mid, high);
        }

    }


    protected void merge(int[] array, int low, int middle, int high)
            throws Exception
    {
        markBox(low, high);

        for (int i = low; i <= middle; i++) {
            copy(aux, i, array, i);
        }
        for (int j = middle + 1; j <= high; j++) {
            copy(aux, high + (middle + 1) - j, array, j);
        }

        for (int k = low, i = low, j = high; k <= high; k++) {
            if (greater(aux, i, j)) {
                copy(array, k, aux, j--);
            }
            else {
                copy(array, k,aux, i++);
            }
        }
    }

    protected void registerSpecificVariables(AlgorithmMonitorModel monitorModel) {
        //todo IMPLEMENT!
    }

}


